Implement strStr

Time: O(N + K); Space: O(K); easy

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = “hello”, needle = “ll”

Output: 2

Example 2:

Input: haystack = “aaaaa”, needle = “bba”

Output: -1

Clarification: 1. What should we return when needle is an empty string? This is a great question to ask during an interview. 2. For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

1. KMP algorithm

Wiki of KMP algorithm: http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm

[2]:

class Solution1(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not needle:
            return 0

        return self.KMP(haystack, needle)

    def KMP(self, text, pattern):
        prefix = self.getPrefix(pattern)
        j = -1
        for i in range(len(text)):
            while j > -1 and pattern[j + 1] != text[i]:
                j = prefix[j]
            if pattern[j + 1] == text[i]:
                j += 1
            if j == len(pattern) - 1:
                return i - j
        return -1

    def getPrefix(self, pattern):
        prefix = [-1] * len(pattern)
        j = -1
        for i in range(1, len(pattern)):
            while j > -1 and pattern[j + 1] != pattern[i]:
                j = prefix[j]
            if pattern[j + 1] == pattern[i]:
                j += 1
            prefix[i] = j
        return prefix

[3]:

s = Solution1()
haystack = "hello"
needle = "ll"
assert s.strStr(haystack, needle) == 2
haystack = "aaaaa"
needle = "bba"
assert s.strStr(haystack, needle) == -1

[6]:

class Solution2(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        try:
            return haystack.index(needle)
        except:
            return -1

[7]:

s = Solution2()
haystack = "hello"
needle = "ll"
assert s.strStr(haystack, needle) == 2
haystack = "aaaaa"
needle = "bba"
assert s.strStr(haystack, needle) == -1

[8]:

class Solution3(object):
    """
    Time: O(N * K)
    Space: O(k)
    """
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        for i in range(len(haystack) - len(needle) + 1):
            if haystack[i : i + len(needle)] == needle:
                return i
        return -1

[9]:

s = Solution3()
haystack = "hello"
needle = "ll"
assert s.strStr(haystack, needle) == 2
haystack = "aaaaa"
needle = "bba"
assert s.strStr(haystack, needle) == -1